膜法森林2333……
显然是一道 LCT 动态加边的题目。
然而并不需要这么高深的数据结构来动态加边(实际上是不会),我们只需要 Spfa 动态加边即可切掉此题。
怎么 Spfa?又是个怎么的动态加边法呢?
在下面我先给出代码,然后再来一步一步剖析(跟 Spfa 板子差不多)。
Code:
1 |
|
动态加边,顾名思义,就是按最优顺序依次将边插入,对于每次插完边的图做一次答案统计(Spfa),然后每次在 main 函数里统计答案,最后输出即可。
我们固定 v1 ,用 v2 跑 Spfa,边的插入顺序是按照 v1 的大小来的,小的先插。
之所以上面要用到 sort,是因为我们要达到”按最优顺序依次将边插入”。
Spfa 的板子就不解释了,不懂的同学左转搜素 Spfa ,先刷几道黄牌去吧……
我们来看看动态加边的过程:
1 | for(int i=1;i<=m;++i){ |
make_line(L[i].x,L[i].y,L[i].v1,L[i].v2);
:
- 加边,不解释
spfa(L[i].x,L[i].y);
:
Spfa 过程。
Q :为什么要定义两个起点 L[i].x 和 L[i].y 呢?
A :显然加进来了这条边后,对当前图中一些点的 dis 值可能会有影响,所以以这个边的两端的点为起点,依次更新旁边的点,直到不能再更新。
ans=min(ans,dis[n]+L[i].v1);
:
更新 ans 值
Q :为什么使用 dis[n]+L[i].v1 对 ans 进行更新,有可能这条最短路上并不包含这个边啊,为什么要将 L[i].v1 算进去呢?可能会更新错答案啊。
A :对于当前图的最短路,我们分两种情况来讨论:
- 1. 这条最短路上没包含这条新加上的边
- 2. 这条最短路上包含了这条新加上的边
对于第一种情况,显然这条最短路在加上这条边之前就已经有了,因为这条边的存在跟这条最短路没任何关系,既然之前有了,那么就肯定已经更新过 ans 了。而那个时候的 v1 是肯定比这个时候的 v1 小的,也就是说 ans 在之前已经被比现在的答案更小的答案更新过了,所以 ans 也不会被当前答案更新。
对于第二种情况,因为这条最短路上包含了这条边,而这条边肯定是这条最短路上 v1 最大的边(当然也是当前图上 v1 最大的边),所以直接更新没错。
每一次循环后数组不要重置吗?
显然队列是不要的,因为 Spfa 的退出条件是是队列为空,所以每次做完 Spfa 时队列也就空了。
vis 数组也不需要,跟队列是一个道理,只有 vis 数组里面还有 true 的元素,说明还有元素在队列里,队列空了,vis 数组也自然空了。
dis 数组不需要,因为循环中每次跑 Spfa 是为了更新 dis 数组而非做最短路。
然后……然后就没有然后了……
本文标题:【题解】 [NOI2014]魔法森林 动态加边Spfa bzoj3669/luogu2387
文章作者:Qiuly
发布时间:2019年02月13日 - 00:00
最后更新:2019年03月29日 - 13:53
原始链接:http://qiulyblog.github.io/2019/02/13/[题解]luoguP2387/
许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。
v1.5.2